import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class RandomList {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public static void main(String[] args) {

    }
    public static Node copyRandomList(Node head) {
        Map<Node,Node> hashmap = new HashMap<>();
        Node cur = head;
        while (cur != null){
            Node node = new Node(cur.val);
            hashmap.put(cur,node);
            cur = cur.next;
        }
        cur = head;
        while (cur != null){
            hashmap.get(cur).next = hashmap.get(cur.next);
            hashmap.get(cur).random = hashmap.get(cur.random);
            cur = cur.next;
        }
        return hashmap.get(head);
    }
}
